/*  给定一个单链表 L(a1, a2, a3, ... ,an),将其重新排列为(a1, an, a2, an-1, ...) */

#include <iostream>
#include "headfun.h"
using namespace std;

// 将链表对半拆分，并将后半段链表倒序
Linklist divrev(LNode *&L)
{
  // 创建快慢指针
  LNode *p = L, *q = L;
  
  // 快指针到达链表尾部，慢指针到达一半
  while (q != NULL && q->next != NULL)
  {
    p = p->next;
    q = q->next->next;
  }
  
  // 创建头结点
  LNode *L1 = new LNode;
  
  // 更新链接
  L1->next = p->next;
  p->next = NULL;
  
  // 链表L1的辅助指针
  LNode *p1 = L1->next, *r;
  L1->next = NULL;
  
  // 遍历链表L1，将L1链表倒序 -- 头插法
  while (p1 != NULL)
  {
    r = p1->next;
    p1->next = L1->next;
    L1->next = p1;
    p1 = r;
  }
  
  // 返回
  return L1;
}

// 链表重排
void merge(LNode *&L)
{
  LNode *r, *s;
  
  // 获取链表L的后半段，经过倒序的链表L1
  LNode *L1 = divrev(L);
  
  // 指向两个链表
  LNode *p = L->next, *q = L1->next;
  
  L1->next = NULL;
  
  // 遍历两个链表
  while (q != NULL)
  {
    // 记录下一个结点
    r = p->next;
    s = q->next;
    
    // 更新链接
    p->next = q;
    q->next = r;
    
    // 指向下一个结点
    p = r;
    q = s;
  }
}

int main()
{
  // 创建带头节点的链表
  LNode *L = head_Linklist();
  
  // 链表重排
  merge(L);
  
  // 打印信息
  L = L->next;
  while (L != NULL)
  {
    cout << L->data << " ";
    L = L->next;
  }
}